package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/8/21 5:09 下午
 */
public class MinDistance {


    public static void main(String[] args) {

        MinDistance exe=new MinDistance();

        String word1="horse";
        String word2="ros";
        int ret= exe.minDistance(word1,word2);

        System.out.println(ret);
    }

    public int minDistance(String word1, String word2) {

        //都为空 直接返回0
        if (word1 == null && word2 == null) {
            return 0;
        }
        // word2 为 空  删除word1 需要多少步
        if (word2 == null || word2.length() == 0) {
            return word1.length();
        }

        //word1 为空  插入 需要多少步
        if (word1 == null || word1.length() == 0) {
            return word2.length();
        }

        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //min(插入、删除、替换)
                    dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1);
                }
            }
        }

        return dp[m][n];
    }


    public int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}
